/// https://leetcode-cn.com/problems/search-in-rotated-sorted-array
pub struct Solution;

impl Solution {
    /// 执行用时： 0 ms , 在所有 Rust 提交中击败了 100.00% 的用户
    /// 内存消耗： 2 MB , 在所有 Rust 提交中击败了 87.72% 的用户
    /// 时间复杂度：最差 O(n) ；空间复杂度：O(1)
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        nums.iter()
            .enumerate() // 不使用 position：因为只需要第一个位置
            .find(|&(_, x)| *x == target)
            .map(|(i, _)| i as i32)
            .unwrap_or(-1)
    }

    /// 执行用时： 0 ms , 在所有 Rust 提交中击败了 100.00% 的用户
    /// 内存消耗： 2 MB , 在所有 Rust 提交中击败了 66.67% 的用户
    /// 时间复杂度：O(log n) ；空间复杂度：O(1)
    /// 重点在于把区间固定在有序且存在目标值的范围内
    /// 这里把每次的中点变成下一次的端点，边界值一次性考虑
    pub fn search_dichotomy(nums: Vec<i32>, target: i32) -> i32 {
        let n = nums.len();
        if nums.get(0).map(|&x| x == target && n == 1).unwrap_or(false) {
            return 0; // 1 <= n <= 5000
        }

        let (mut mid, mut i, mut j) = (n / 2, 0, n - 1);
        // println!("{} target = {}", "-".repeat(20), target);
        while i < j {
            // vec_pos!(nums; i=i,k=mid,j=j);
            if nums[i] <= nums[mid] {
                // 前半段有序
                if nums[i] <= target && target <= nums[mid] {
                    j = mid; // 前半段
                } else {
                    i = mid; // 后半段
                }
            } else {
                // 后半段有序
                if nums[mid] <= target && target <= nums[j] {
                    i = mid; // 后半段
                } else {
                    j = mid; // 前半段
                }
            }

            if nums[i] == target {
                return i as i32;
            } else if nums[j] == target {
                return j as i32;
            } else {
                mid = (i + j) / 2;
                if i == mid || j == mid {
                    return -1;
                }
            }
        }
        -1 // i = j = 0 即 n = 1 时
    }

    /// 执行用时： 0 ms , 在所有 Rust 提交中击败了 100.00% 的用户
    /// 内存消耗： 2.1 MB , 在所有 Rust 提交中击败了 17.54% 的用户
    /// 这个是官方给的解答，相比于上面的二分法：答案在边界上时指针会多移动一次
    /// 每次把中点作为下一次的端点，而且把一半边界缩小一位，另一半边界固定，在边界值上略复杂
    /// https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/sou-suo-xuan-zhuan-pai-xu-shu-zu-by-leetcode-solut/
    pub fn search_dichotomy_leet(nums: Vec<i32>, target: i32) -> i32 {
        let n = nums.len();
        if nums.get(0).map(|&x| x == target && n == 1).unwrap_or(false) {
            return 0; // 1 <= n <= 5000
        }

        let (mut mid, mut i, mut j) = (n / 2, 0, n - 1);

        // println!("{} target = {}", "-".repeat(20), target);
        while i <= j {
            // vec_pos!(nums; i=i,k=mid,j=j);
            if nums[mid] == target {
                return mid as i32;
            }
            if nums[0] <= nums[mid] {
                // 前半段有序
                if nums[0] <= target && target < nums[mid] {
                    j = mid - 1;
                } else {
                    i = mid + 1;
                }
            } else {
                // 后半段有序
                if nums[mid] < target && target <= nums[n - 1] {
                    i = mid + 1;
                } else {
                    j = mid - 1;
                }
            }
            mid = (i + j) / 2;
        }
        -1
    }

    /// 执行用时： 0 ms , 在所有 Rust 提交中击败了 100.00% 的用户
    /// 内存消耗： 2.2 MB , 在所有 Rust 提交中击败了 5.26% 的用户
    /// 思路和 leet 答案差不多，除了区间端点不同
    /// https://rustgym.com/leetcode/33
    pub fn search_dichotomy_gym(nums: Vec<i32>, target: i32) -> i32 {
        let n = nums.len();
        let mut l = 0;
        let mut r = n - 1;
        while l <= r {
            let m = (l + r) / 2;
            if target == nums[m] {
                return m as i32;
            } else if nums[l] <= nums[m] {
                if nums[l] <= target && target < nums[m] {
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            } else {
                if nums[m] < target && target <= nums[r] {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
        }
        -1
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn assert<F>(f: F)
        where F: Fn(Vec<i32>, i32) -> i32 {
        let v = vec![4, 5, 6, 7, 0, 1, 2];
        assert_eq!(f(v.clone(), 0), 4);
        assert_eq!(f(v.clone(), 4), 0);
        assert_eq!(f(v, 3), -1);
        assert_eq!(f(vec![1], 0), -1);
        assert_eq!(f(vec![1, 0], 0), 1);
        assert_eq!(f(vec![1, 0], 2), -1);
    }

    bench!(assert Solution::search);
    bench!(assert Solution::search_dichotomy);
    bench!(assert Solution::search_dichotomy_leet);
    bench!(assert Solution::search_dichotomy_gym);
}
